package com.wzw.basics.sort;

import java.util.Arrays;

/**
 * 插入排序: 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
 *
 * @author Wangzhiwen
 */
public class InsertionSort {

    /*
     * 从前往后，假设前面的元素已是有序集合A[]。后面的元素从后往前依次和A[]进行比较，如果小于某一个值就和他交换位置
     * 10,3,123,43,56,12,9 length=7 [0,6]
     *
     * i=0 toBeCompared=3 raw arrays [10, 3, 123, 43, 56, 12, 9] orderly arrays [10]
     * produced by comparing arrays [10, 10, 123, 43, 56, 12, 9]
     * after the exchange arrays [3, 10, 123, 43, 56, 12, 9]
     *
     * i=1 toBeCompared=123 raw arrays [3, 10, 123, 43, 56, 12, 9] orderly arrays [3, 10]
     * after the exchange arrays [3, 10, 123, 43, 56, 12, 9]
     *
     * i=2 toBeCompared=43 raw arrays [3, 10, 123, 43, 56, 12, 9] orderly arrays [3, 10, 123]
     * produced by comparing arrays [3, 10, 123, 123, 56, 12, 9]
     * after the exchange arrays [3, 10, 43, 123, 56, 12, 9]
     *
     * i=3 toBeCompared=56 raw arrays [3, 10, 43, 123, 56, 12, 9] orderly arrays [3, 10, 43, 123]
     * produced by comparing arrays [3, 10, 43, 123, 123, 12, 9]
     * after the exchange arrays [3, 10, 43, 56, 123, 12, 9]
     *
     * i=4 toBeCompared=12 raw arrays [3, 10, 43, 56, 123, 12, 9] orderly arrays [3, 10, 43, 56, 123]
     * produced by comparing arrays [3, 10, 43, 56, 123, 123, 9]
     * produced by comparing arrays [3, 10, 43, 56, 56, 123, 9]
     * produced by comparing arrays [3, 10, 43, 43, 56, 123, 9]
     * after the exchange arrays [3, 10, 12, 43, 56, 123, 9]
     *
     * i=5 toBeCompared=9 raw arrays [3, 10, 12, 43, 56, 123, 9] orderly arrays [3, 10, 12, 43, 56, 123]
     * produced by comparing arrays [3, 10, 12, 43, 56, 123, 123]
     * produced by comparing arrays [3, 10, 12, 43, 56, 56, 123]
     * produced by comparing arrays [3, 10, 12, 43, 43, 56, 123]
     * produced by comparing arrays [3, 10, 12, 12, 43, 56, 123]
     * produced by comparing arrays [3, 10, 10, 12, 43, 56, 123]
     * after the exchange arrays [3, 9, 10, 12, 43, 56, 123]
     *
     * insertion sort [3, 9, 10, 12, 43, 56, 123]
     *
     */
    public static void execute(int[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }
        // 1.记录需要被比较的元素值
        int toBeCompared;
        for (int i = 0; i < arrays.length - 1; i++) {

            System.out.print("i=" + i);

            // 被比较的元素值为下标索引i+1，即下一个元素（前面元素是有序的后面元素是无序的，后面的需要和前面的元素作比较）
            toBeCompared = arrays[i + 1];
            // 前一个元素的下标值，它是有序数组的最后一个
            int preIndex = i;

            System.out.print(" toBeCompared=" + toBeCompared);
            System.out.print(" raw arrays " + Arrays.toString(arrays));
            System.out.println(" orderly arrays " + Arrays.toString(Arrays.copyOf(arrays, preIndex+1)));

            // 当前需要排序的元素和之前已排好序的元素从后往前依次比较，如果它小于了前面有序数组中的一个就交换
            while (preIndex >= 0 && toBeCompared < arrays[preIndex]) {
                // 把前面有序数组的值赋给它后面这个元素
                arrays[preIndex + 1] = arrays[preIndex];

                System.out.println("produced by comparing arrays " + Arrays.toString(arrays));

                preIndex--;

            }
            //
            arrays[preIndex + 1] = toBeCompared;

            System.out.println("after the exchange arrays " + Arrays.toString(arrays));
        }

        System.out.println("insertion sort " + Arrays.toString(arrays));
    }

}
